This invention relates to the field of geometric modeling. More specifically, the invention relates to computation, visualization and/or annotation of geometric models.
In CAD/CAM and other areas, one needs to view and interact with 3D models obtained from a local machine or a remote server. These 3D models contain both geometry to define their shapes and surface features, such as color and annotations. Some annotations correspond to a two-dimensional figure mapped onto the surface of the geometric model. In order to improve performance, there is also a growing need to represent these complex three-dimensional models by simplified versions that are less expensive to store in memory on a computer, faster to transmit across a network from one computer to another computer, and faster to render on a computer. To address this, many techniques have been developed to simplify a model with minimal loss in perceived quality. See, for example, U.S. Pat. No. 5,929,860 or the article xe2x80x9cSurface Simplification Using Quadric Error Metrics,xe2x80x9d by M. Garland and P. Heckbert, in Computer Graphics Proceedings, Annual Conference Series, 1997, pages 209-216. Such techniques attempt to reduce the geometry of the model so that when the simplified model is rendered on a computer, the viewer will be able to perceive few, if any, differences as compared to a rendering of the original model. To accomplish this goal, many of the simplification techniques take the attributes of the model into account as well when simplifying the geometry. See, for example, U.S. Pat. No. 6,100,902; P. Cignoni, C. Montani, C. Rocchini, and R. Scopigno, xe2x80x9cA General Method for Preserving Attribute Values on Simplified Meshesxe2x80x9d, Proceedings of IEEE Visualization, pages 59-66, 1998; M. Garland and P. Heckbert, xe2x80x9cSimplifying Surfaces with Color and Texture Using Quadric Error Metrics,xe2x80x9d Proceedings of IEEE Visualization, pages 264-269, 1998; and H. Hoppe, xe2x80x9cNew Quadric Metric for Simplifying Meshes with Appearance Attributes,xe2x80x9d Proceedings of IEEE Visualization, pages 59-66, 1999. These techniques let the attributes guide the simplification process so that the geometry and the attributes of the simplified model appear the same as in the original model. To further preserve the overall appearance of the model, the annotations must be mapped onto the simplified model when simplification techniques are utilized, since the annotations can convey a significant amount of information.
A conventional way to perform the mapping from an image to the surface of an object is called, xe2x80x9ctexture mappingxe2x80x9d and is commonly used to represent features with high detail on a surface containing few polygons. If the object to be mapped onto a nearby surface corresponds to a geometric mesh, comprised of vertices connected by lines, then the use of texture mapping to depict that mesh on the new surface would require rendering the mesh and then texture mapping it onto the surface. Although there are established techniques for texture mapping surface features onto an object, they do not separate the annotative texture from the contextual texture. Texture mapping, thoroughly described by P. Heckbert in xe2x80x9cSurvey of Texture Mappingxe2x80x9d, IEEE Computer Graphics and Applications, volume 6, number 11, pages 56-67, November 1986, refers to a technique for mapping an image onto the surface of a model. Texture mapping has been commonly used to map annotations onto the surface of a model. To accomplish this, the annotations are first rendered as an image and stored in the memory of a computer. When the model is being viewed, the texture map of the annotations is applied to the surface of the model to convey the additional information provided by the annotations. Using such an approach, the annotations of a model can be mapped onto the original or simplified surface of the model, since they are stored in the form of an image.
D. Eu and G. T. Toussaint, in xe2x80x9cOn approximating polygonal curves in two and three dimensions.xe2x80x9d CVGIP: Graph. Models Image Process., 56(3):231-246, May 1994, describe techniques for simplifying paths in space using a xe2x80x9cparallel stripxe2x80x9d concept that results in a simplified version of the original path in three-dimensions that does not depart from the original path by more than the allowed tolerance. G. Barequet, D. Chen, O. Daescu, M. Goodrich, and J. Snoeyink in xe2x80x9cEfficiently approximating polygonal paths in three and higher dimensions,xe2x80x9d Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 317-326, 1998, describe a refined algorithm for simplifying paths in three-dimensions more efficiently.
Texture mapping requires specialized graphics hardware for adequate performance during viewing, and that hardware is not currently guaranteed to be present on all computers. In addition, texture mapping requires rendering one or more views of the annotations from different viewpoints, and projecting the rendered images onto the surface via texture coordinates. When multiple images are used to represent the annotations of the model at the same time, differences in rendering parameters between images may result in a discontinuity where the images border each other and this discontinuity can stand out as a disturbing artifact. Annotations that do not appear seamless may be hard to interpret because the eye is drawn to the abrupt changes in surface characteristics rather than the actual features on the surface. Consequently, the annotations may become an ineffective means for conveying the additional information to the viewer.
Texture maps also suffer from blurring and pixelization at high magnification. Since the annotations are stored as an image, they are recorded at a fixed resolution. Typically the resolution of the image is measured in terms of the number of pixels in width and height. If the viewer zooms into the model to see the surface details more closely, the annotations texture map will appear blurry and unnatural. When surface annotations become blurred at high magnifications, they lose their impact as informative surface markup, and instead appear as an unnatural image pasted onto the surface. When the annotations are integral with the texture map, they lose their visual impact as surface markup and merge with the background features in a way that detracts from, rather than enhances, their visual importance. The end result is that the information conveyed by the annotations will be lost by the viewer.
Texture maps are most efficient for simple geometric models. For complex models, many additional images, from different viewpoints, will be required. This will greatly exacerbate the discontinuity problem mentioned previously.
Existing techniques for simplifying paths in two- and three-dimensions do not account for paths that are attached to surfaces, nor do they allow different sensitivities to error tangent and perpendicular to the surface. This leads to annotations that are either under-simplified, or prone to penetrate or float above the surface in an artificial manner.
An object of this invention is an improved system and method to simplify annotations on a surface.
An object of this invention is an improved system and method to simplify the number of line segments used as annotations on a surface.
An object of this invention is an improved system and method to simplify the number of line segments used as annotations on a surface using a directed asymmetric tolerance window that allows a different degree of simplification in the plane tangent to the surface, compared to the tolerance perpendicular to the surface.
The present invention is a computer system and method for simplifying annotations on a surface. A tolerance process creates a tolerance window lying in a plane and centered on the query point at the end of a test edge and perpendicular to the test edge. The tolerance window is defined by a first tolerance that specifies an amount of first error measured by the distance from a simplified path to an original path in the plane tangent to the surface and a second tolerance specifies an amount of second error measure by the distance from the simplified path to the original path in the plane perpendicular to the surface. The original path is a set of original edges on the surface. A point projection process that projects a second end point of one or more second edges onto the plane of the tolerance window. The second edges has the query point also as an end point where the projection of the second end points are projected points. An invalidation process marks an edge as xe2x80x9cinvalidxe2x80x9d and removes it both from the list of simplifiable edges and the final list of simplified edges. A selection process selects one of the second end points that has a projected point within the plane containing the tolerance window, deletes the query point, and connects the origin point to the respective second end point, to create a new edge that replaces the test edge and respective second edges in the set of original edges to create the simplified path.